package huisu;

import java.util.List;

/**
 * 给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
 *
 * 示例 1：
 *
 * 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
 * 输出： True
 * 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
 *  
 */
public class leetCode698_canPartitionKSubsets {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if(nums.length == 0) return false;
        if (k > nums.length) return false;
        int sum = 0;
        int maxNum = 0;
        for (int num : nums) {
            sum += num;
            if(num > maxNum){
                maxNum = num;
            }
        }
        if(maxNum > sum/k) return false;
        if(sum % k != 0) return false;

        // k 个桶（集合），记录每个桶装的数字之和
        int[] bucket = new int[k];
        // 理论上每个桶（集合）中数字的和
        int target = sum/k;

        // 穷举，看看 nums 是否能划分成 k 个和为 target 的子集
        return build(nums,0,bucket,target);


    }


    public boolean build(int[] nums, int index, int[] bucket,int target){
        if(index == nums.length){
            for (int i : bucket) {
                if(i != target){
                    return false;
                }
            }
            return true;
        }

        for (int i = 0; i < bucket.length; i++) {
            if (bucket[i] + nums[index] > target) {
                continue;
            }
            bucket[i] += nums[index];
            if(build(nums,index + 1,bucket,target)){
                return true;
            }
            bucket[i] -= nums[index];

        }
        return false;
    }

    public boolean canPartitionKSubsets2(int[] nums, int k) {
        if(nums == null || nums.length == 0) return false;
        if (k > nums.length) return false;
        int max = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            max = Math.max(max,nums[i]);
        }
        if(max > sum/k){
            return false;
        }
        if(sum % k != 0){
            return false;
        }

        int[] bucket = new int[k];
        int target = sum/k;
        return build2(nums,0,bucket,target);

    }


    public boolean build2(int[] nums, int index, int[] bucket,int target){
       if(index == nums.length){
           for (int i : bucket) {
               if(i != target){
                   return false;
               }
           }
           return true;
       }

        for (int i = 0; i < bucket.length; i++) {
            if(bucket[i] + nums[index] > target){
                continue;
            }
            bucket[i] += nums[index];
            if(build2(nums,index + 1,bucket,target)){
                return true;
            }
            bucket[i] -= nums[index];
        }

        return false;
    }
}
